package exercises.newcoder.solution;

import java.util.Scanner;

/**
 * <a href="https://www.nowcoder.com/study/live/716/5/16">
 *     折纸问题 - 二叉树习题 - 牛客算法课</a>
 * @author or2
 * @Description 请把一张纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。给定一个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向。
 * @create 2021年09月09日 时间: 9:33
 */
public class PaperFolding {

//    直接使用默认 sout 会超时
    private static final StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int times = scanner.nextInt();
        inOrder(0, times, true);
        System.out.println(stringBuilder);
    }

    private static void inOrder(int level, int totalTimes, boolean down) {
        if (level < totalTimes) {
            inOrder(level + 1, totalTimes, true);
            stringBuilder.append(down ? "down\n" : "up\n");
            inOrder(level + 1, totalTimes, false);
        }
    }
}
